package com.duanjw.algorithms;

/**
 * 最大公约数
 *
 * @author duanjw
 */
public class Gcd {
    public static void main(String[] args) {
        System.out.println(gcd(96, 108));
    }

    /**
     * 计算两个非负整数p和q的最大公约数
     * 若q是0，则最大公约数为p，否则，将p除以q得到的余数r，p和q的最大公约数即为q和r的最大公约数
     *
     * @param p
     * @param q
     */
    public static int gcd(int p, int q) {
        if (q == 0) {
            return p;
        }
        int r = p % q;
        System.out.println(q + "," + r);
        return gcd(q, r);
    }
}
